package com.example.algorithm.tree;

import java.util.*;

/**
 * @author : zhy
 * @since : 2022/7/29
 * 二叉树层次遍历
 */
public class Arrangement {


    /**--------------------------迭代方法--------------------------------*/
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null)
        {
            return list;
        }
        arrForeach(root);
        return list;

    }
    private void arrForeach(TreeNode root) {
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty())
        {
            int len=queue.size();
            ArrayList<Integer> arrayList = new ArrayList<>();
            while(len>0)
            {
                TreeNode node= queue.poll();
                arrayList.add(node.val);
                if(node.left!=null)
                {
                    queue.offer(node.left);
                }
                if(node.right!=null)
                {
                    queue.offer(node.right);
                }
                len--;
            }
            list.add(arrayList);
        }
    }



    /**--------------------------递归方法--------------------------------*/
    List<List<Integer>> list1=new ArrayList<>();
    public List<List<Integer>> levelOrder1(TreeNode root)
    {
        arrForeach1(root,0);
        return list1;
    }

    private void arrForeach1(TreeNode root, int deep) {
        if(root==null) {
            return;
        }
        deep++;
        if(list1.size()<deep)
        {
            ArrayList<Integer> arrayList = new ArrayList<>();
            list1.add(arrayList);
        }
        list1.get(deep-1).add(root.val);
        arrForeach1(root.left,deep);
        arrForeach1(root.right,deep);
    }
}
